package cn.hchaojie.camp.week1;

import java.util.Random;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/random-pick-index/description/
 * 蓄水池抽样算法
 * 
 * @author hchaojie
 *
 */
public class ReservoirSampling {
	private static final int[] DATA = {
		1,2,3,3,3
		//1
	};
	
	@Test
	public void test() {
		for (int i = 0; i < 100; i++) {
			// System.out.println("找到一个：" + pick(DATA, 1));
			System.out.println("找到一个：" + pick(DATA, 3));
		}
	}
	
	public int pick(int[] array, int target) {
		// 找到第一个，第一个返回的概率是 1 / 1. （注意这时候不返回）
		// 找到第二个，以1/2概览返回当前，以1/2概率返回前面一个

		// 找到第三个，以1/3概率返回当前， 2/3 (返回前面两个里面任意一个的概率是 2 /3)  1/2 * 2/3 = 1/3
		// 以2/3概率返回前两个中的任意一个
		
		int index = 0;				// 数组的遍历下标
		int foundCount = 0;			// 当前已经找到多少个了
		int result = -1;
		while (index < array.length) {
			if (target == array[index]) {
				foundCount++;
				
				double p = 1 / (double) foundCount;
				if (Math.random() < p) {
					result = index;
				}
			}
			
			index++;
		}
		
		

		return result;
    }
}
